package BackTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * Copyright (C) 2015 THL A29 Limited, a Tencent company. All rights reserved.
 *
 * @author v_mhanzhou 2021/6/15
 */
public class N皇后51_1 {
    List<List<int[]>> res =new ArrayList<>();
    List<int[]> tmp = new ArrayList<>(); // 4个坐标 一个答案
    int[][] gird ;
    int n;
    int[][] ziGird;


    public List<List<int[]>> solveNQueens(int n) {
        this.n = n;
        gird = new int[n][n];
        ziGird = new int[n][n]; // 记录放棋子

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                // 定起点
                System.out.println(String.format("\n -> 定起点 %s,%s\n",
                        i,j
                ));

                colored(i,j);
                System.out.println("初始");

                ptGird(gird);
                ziGird[i][j] = 1;
                tmp.add(new int[]{i,j});

                backTrack(i, j);

                ziGird[i][j]=0;
                uncolored(i,j);
                tmp.remove(0);
            }
        }
        return res;
    }
    public void ptGird(int[][] gird){
        for (int i = 0; i < gird.length; i++) {
            for (int j = 0; j < gird.length ; j++) {
                System.out.print(gird[i][j] + " ");
            }
            System.out.println();
        }
    }
    public void colored(int x, int y){
        for (int i = 0; i < gird.length; i++) {
            gird[i][y] = 1;
        }
        for (int i = 0; i < gird.length; i++) {
            gird[x][i] = 1;
        }
    }
    public void uncolored(int x, int y){
        for (int i = 0; i < gird.length; i++) {
            gird[i][y] = 0;
        }
        for (int i = 0; i < gird.length; i++) {
            gird[x][i] = 0;
        }
    }
    public boolean canPut(int x, int y){
        for (int i = 0; i < n; i++) {
            if(ziGird[x][i] == 1)
                return false;
        }
        for (int i = 0; i < n; i++) {
            if(ziGird[i][y] == 1)
                return false;
        }
        return true;
    }
    public void backTrack(int x, int y){
        if(tmp.size() == n){
            res.add(new ArrayList<>(tmp));
            return;
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(gird[i][j] == 1) continue;
                // 看看能不能放
                if(canPut(i, j) == false) continue;

                //放子
                ziGird[i][j] = 1;
                //涂色 这里gird类似vis (自己本身也涂了)
                colored(i, j);
                System.out.println("--涂色后---- x:"+x+",y:"+y);
                ptGird(gird);
                System.out.println("------");

                tmp.add(new int[]{i,j});
                backTrack(i,j);

                //去子
                ziGird[i][j] = 0;
                //去色
                uncolored(x, y);
                System.out.println("--去色后---- x:"+x+",y:"+y);
                ptGird(gird);
                System.out.println("------");
                tmp.remove(tmp.size()-1);
            }
        }
    }
    @Test
    public void test(){
//        int[][] gird2 = new int[4][4];
//        ptGird(gird2);
        List<List<int[]>> lists = solveNQueens(3);
        System.out.println("res----");
        for (List<int[]> l : lists){
            for (int i = 0; i < 3; i++) {
                System.out.print(l.get(i)[0]+","+l.get(i)[1] + " ");
            }
            System.out.println();
        }
    }
}
